#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1e3 + 10, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
int dis[N];
bool st[N];
int ans;
int n, m;
void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dij(int x)
{
	priority_queue<PII, vector<PII>, greater<PII>>heap;
	heap.push({ 0,x });
	memset(dis, 0x3f, sizeof(dis));
	memset(st, 0, sizeof(st));
	dis[x] = 0;
	while (heap.size()) {
		PII t = heap.top();
		heap.pop();
		int distance = t.x;
		int ver = t.y;
		if (st[ver])continue;
		st[ver] = 1;
		for (int i = h[ver]; ~i; i = ne[i]) {
			int j = e[i];
			if (dis[j] > w[i] + distance) {
				dis[j] = w[i] + distance;
				heap.push({ dis[j],j });
			}
		}
	}
	//cout << "x==" << x << endl;
	//cout << "dis[6]===" << dis[6] << endl;
	//sort(dis, dis + n + 1);
	//cout << "x==" << x << endl;
	//cout << "dis[6]===" << dis[6] << endl;
	int cnt = 0;
	int ans1 = 0, ans2 = 0;
	for (int i = n; i >= 1; i--) {
		if (i != x && dis[i] != 0x3f3f3f3f) {
			cnt++;
			if (dis[i] > ans1) {
				ans2 = ans1;
				ans1 = dis[i];
			}
			else if (dis[i] > ans2) {
				ans2 = dis[i];
			}
			/*cout << "i==" << i << endl;
			cout << "x==" << x << endl;
			cout << "dis[i]==" << dis[i] << endl;*/
			//ans += dis[i];
			//if (cnt == 2)break;
		}
	}
	ans = ans1 + ans2;
	if (cnt < 2)return 0;
	return 1;
}
int main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> m;
		memset(h, -1, sizeof(h));
		memset(e, 0, sizeof(e));
		memset(ne, 0, sizeof(ne));
		memset(w, 0, sizeof(w));
		idx = 0;
		ans = 0;
		while (m--) {
			int a, b, c;
			cin >> a >> b >> c;
			add(a, b, c);
			add(b, a, c);
		}
		int res = -1;
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (dij(i)) {
				//cout << "ans==" << ans << endl;
				res = max(ans, res);
			}
			else cnt++;
		}
		if (cnt == n)cout << -1 << endl;
		else cout << res << endl;
	}
	return 0;
}